package com.zxx.casserver;

import java.util.*;

/**
 * @author: zhoukai
 * @date: 2022/3/30 15:13
 */
public class Tree {
    public static TreeNode makeTree() {
        TreeNode root = new TreeNode("A", null);

        TreeNode B = new TreeNode("B", root);
        TreeNode C = new TreeNode("C", root);
        TreeNode D = new TreeNode("D", root);

        root.addChild(B);
        root.addChild(C);
        root.addChild(D);

        TreeNode E = new TreeNode("E", B);
        TreeNode F = new TreeNode("F", B);

        B.addChild(E);
        B.addChild(F);

        TreeNode G = new TreeNode("G", D);

        D.addChild(G);


        TreeNode H = new TreeNode("H", E);
        TreeNode I = new TreeNode("I", E);
        TreeNode J = new TreeNode("J", E);

        E.addChild(H);
        E.addChild(I);
        E.addChild(J);

        return root;
    }

    /**
     * 广度优先需要构建一个先进先出的队列
     *
     * @param root
     */
    public static void breadthFirst(TreeNode root) {
        Deque<TreeNode> nodeDeque = new LinkedList<>();
        TreeNode node = root;
        nodeDeque.add(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            System.out.println(node.getName());
            nodeDeque.addAll(node.getChildren());
        }

    }

    /**
     * 深度优先需要构建一个后进先出的栈
     *
     * @param root
     */
    public static void depthFirst(TreeNode root) {
        Deque<TreeNode> nodeDeque = new LinkedList<>();
        TreeNode node = root;
        nodeDeque.push(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            System.out.println(node.getName());
            List<TreeNode> children = node.getChildren();
            //注意这里要从后向前遍历
            for (int i = children.size() - 1; i >= 0; i--) {
                nodeDeque.push(children.get(i));
            }
        }
    }


    public static List<List<String>> levelOrder2 (TreeNode root){
        List<List<String>> result = new ArrayList<>();
        if (null == root) {
            return result;
        }

        // 临时队列其实就是每一层的节点
        Queue<TreeNode> temp = new LinkedList<>();
        temp.offer(root);
        while (!temp.isEmpty()) {
            // 当前层节点的数量
            int size = temp.size();
            List<String> levelOrderId = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = temp.poll();
                // 将该节点移除，并加入当前层节点中
                levelOrderId.add(poll.getName());
                // 这里将所有不为空的子节点全部放入temp临时队列里
                List<TreeNode> children = poll.getChildren();
                if (null != children && 0 < children.size()) {
                    temp.addAll(children);
                }
            }
            // 将每一层节点当作一个元素加入最终返回结果里
            result.add(levelOrderId);
        }
        System.out.println(result);
        return result;
    }


    public static void main(String[] args) {
        TreeNode root = makeTree();
        levelOrder2(root);
    }


}

class TreeNode {

    private String name;
    private TreeNode parent;
    private List<TreeNode> children = new ArrayList<>();

    public TreeNode(String name, TreeNode parent) {
        this.name = name;
        this.parent = parent;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getParent() {
        return parent;
    }

    public void setParent(TreeNode parent) {
        this.parent = parent;
    }

    public List<TreeNode> getChildren() {
        return children;
    }

    public void addChild(TreeNode child) {
        children.add(child);
    }
}
